Thực đơn
Thuật_toán_Bellman-Ford Nội dung thuật toánfunction BellmanFord(danh_sách_đỉnh, danh_sách_cung, nguồn) // hàm yêu cầu đồ thị đưa vào dưới dạng một danh sách đỉnh, một danh sách cung // hàm tính các giá trị khoảng_cách và đỉnh_liền_trước của các đỉnh, // sao cho các giá trị đỉnh_liền_trước sẽ lưu lại các đường đi ngắn nhất. // bước 1: khởi tạo đồ thị for each v in danh_sách_đỉnh: if v is nguồn then khoảng_cách(v):= 0 else khoảng_cách(v):= vô cùng đỉnh_liền_trước(v):= null // bước 2: kết nạp cạnh for i from 1 to size(danh_sách_đỉnh)-1: for each (u,v) in danh_sách_cung: if khoảng_cách(v) > khoảng_cách(u) + trọng_số(u,v): khoảng_cách(v):= khoảng_cách(u) + trọng_số(u,v) đỉnh_liền_trước(v):= u // bước 3: kiểm tra chu trình âm for each (u,v) in danh_sách_cung: if khoảng_cách(v) > khoảng_cách(u) + trọng_số(u,v): error "Đồ thị chứa chu trình âm"
Thực đơn
Thuật_toán_Bellman-Ford Nội dung thuật toánLiên quan
Thuật ngữ giải phẫu cử động Thuật toán Thuật ngữ anime và manga Thuật ngữ lý thuyết đồ thị Thuật ngữ thiên văn học Thuật chiêu hồn Thuật toán Dijkstra Thuật ngữ tin học Thuật ngữ ngữ âm học Thuật toán sắp xếpTài liệu tham khảo
WikiPedia: Thuật_toán_Bellman-Ford